import com.sun.xml.internal.ws.server.ServerRtException;

import java.util.ArrayList;

/**
 * Created by L.jp
 * Description:给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
 * 例如，给出n=3，解集为：
 * "((()))", "(()())", "(())()", "()()()", "()(())"
 * User: 86189
 * Date: 2022-08-18
 * Time: 9:22
 */
//总共有n对括号，每出现一个左括号个数就+1,用字符串拼接括号，但是不能动右括号的个数，每出现一个右括号个数就+1，拼接括号，这就是递归，等到个数都达到了n
    //那么就可以把符合的结果加入到最终的结果
public class Solution {
    public ArrayList<String> generateParenthesis (int n) {
         ArrayList<String> ret=new ArrayList<>();
         getCount(0,0,"",ret,n);
         return  ret;
    }
    public void getCount(int left,int right,String tmp,ArrayList<String> ret,int n){
        if(left==n && right==n){
            ret.add(tmp);
            return;
        }
        if(left<n){
            getCount(left+1,right,tmp+"(",ret,n);
        }
        //在右括号小于n的情况小，。必须是右括号的个数小于左括号的个数才保证是合法的
        if(right<n && left>right){
            getCount(left,right+1,tmp+")",ret,n);
        }
    }
}
